<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            function DoublyLinkedList() {
                function Node(data) {
                    this.data = data;
                    this.next = null;
                    this.prev = null;
                }
                this.head = null;
                this.tail = null;
                this.length = 0;

                // append（element）：向链表尾部添加一个新的项；
                DoublyLinkedList.prototype.append = function (element) {
                    var newNode = new Node(element);
                    if (this.length === 0) {
                        this.head = newNode;
                        this.tail = newNode;
                    } else {
                        newNode.prev = this.tail;
                        this.tail.next = newNode;
                        this.tail = newNode;
                    }
                    this.length++;
                };
                // insert（position，element）：向链表的特定位置插入一个新的项；
                DoublyLinkedList.prototype.insert = function (position, element) {
                    var newNode = new Node(element);
                    if (position < 0 || position > this.length) return;
                    if (position === 0) {
                        newNode.next = this.head;
                        this.head.prev = newNode;
                        this.head = newNode;
                    } else if (position === this.length) {
                        this.tail.next = newNode;
                        newNode.prev = this.tail;
                        this.tail = newNode;
                    } else {
                        var current = this.head;
                        for (let i = 0; i < position - 1; i++) {
                            current = current.next;
                        }
                        newNode.next = current.next;
                        newNode.prev = current;
                        current.next.prev = newNode;
                        current.next = newNode;
                    }
                    this.length++;
                };
                // get（position）：获取对应位置的元素；
                DoublyLinkedList.prototype.get = function (position) {
                    if (position < 0 || position >= this.length) return;
                    var current = this.head;
                    for (let i = 0; i < position; i++) {
                        current = current.next;
                    }
                    return current.data;
                };
                // indexOf
                DoublyLinkedList.prototype.indexOf = function (element) {
                    var current = this.head;
                    for (let i = 0; i < this.length; i++) {
                        if (current.data === element) {
                            return i;
                        }
                        current = current.next;
                    }
                    return -1;
                };
                // update（position，element）：修改某个位置的元素；
                DoublyLinkedList.prototype.update = function (position, element) {
                    if (position < 0 || position >= this.length) return;
                    var current = this.head;
                    for (let i = 0; i < position; i++) {
                        current = current.next;
                    }
                    current.data = element;
                };
                // removeAt（position）：从链表的特定位置移除一项；
                DoublyLinkedList.prototype.removeAt = function (position) {
                    if (position < 0 || position >= this.length) return null;
                    var current = this.head;
                    if (this.length == 1) {
                        this.head = null;
                        this.tail = null;
                    } else if (position == this.length - 1) {
                        current = this.tail;
                        this.tail.prev.next = null;
                        this.tail = this.tail.prev;
                    } else if (position == 0) {
                        this.head.next.prev = null;
                        this.head = this.head.next;
                    } else {
                        for (let i = 0; i < position; i++) {
                            current = current.next;
                        }
                        current.next.prev = current.prev;
                        current.prev.next = current.next;
                    }
                    this.length--;
                    return current.data;
                };
                // remove（element）：从链表的移除一项；
                DoublyLinkedList.prototype.remove = function (element) {
                    var index = this.indexOf(element);
                    return this.removeAt(index);
                };
                // isEmpty（）：如果链表中不包含任何元素，返回trun，如果链表长度大于0则返回false；
                DoublyLinkedList.prototype.isEmpty = function () {
                    return this.length > 0 ? false : true;
                };
                // size（）：返回链表包含的元素个数，与数组的length属性类似；
                DoublyLinkedList.prototype.size = function () {
                    return this.length;
                };
                // toString（）：由于链表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值；
                DoublyLinkedList.prototype.toString = function () {
                    return this.forwardString();
                };
                // forwardString（）：返回正向遍历节点字符串形式；
                DoublyLinkedList.prototype.forwardString = function () {
                    var current = this.head;
                    var str = '';
                    while (current) {
                        str += current.data + ' ';
                        current = current.next;
                    }
                    return str;
                };
                // backwordString（）：返回反向遍历的节点的字符串形式；
                DoublyLinkedList.prototype.backwordString = function () {
                    var current = this.tail;
                    var str = '';
                    while (current) {
                        str += current.data + ' ';
                        current = current.prev;
                    }
                    return str;
                };
            }
            var doublyLinkedList = new DoublyLinkedList();
            doublyLinkedList.append('a');
            doublyLinkedList.append('b');
            doublyLinkedList.append('c');
            doublyLinkedList.append('d');
            doublyLinkedList.append('e');
            doublyLinkedList.insert(2, 'f');
            doublyLinkedList.update(5, 'f');
            console.log(doublyLinkedList.indexOf('q'));
            console.log(doublyLinkedList.remove('a'));
            console.log(doublyLinkedList.length);
            console.log(doublyLinkedList.toString());
        </script>
    </body>
</html>
